#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <stdbool.h>
#include <unistd.h>
#include <pthread.h>
#include <semaphore.h>
#include <time.h>

#define NTHREADS 4
#define BUFFSIZE 4*(NTHREADS)
#define DEGREE 4
#define ORDER (DEGREE)

typedef double keyType;
typedef struct BPNode{
	pthread_rwlock_t nodeLock;

	_Bool leaf;
	int numKeys;
	
	struct BPNode *parentNode;//for dependent root or not
	struct BPNode *prevNode;
	struct BPNode *nextNode;
	struct BPNode *childNode[2*ORDER];

	keyType keys[ORDER];
	char dataStr[ORDER][512];//memcpy
}BPNode,*pBPNode;

typedef struct lockBuf_t{
	pBPNode lockQueueBuf[64];//1048576
	pthread_mutex_t lockBufLock;
	int head;
	int tail;
}lockBuf_t;
//lockBuf_t lockBuf;
//thread_mutex_t lockBufLock = PTHREAD_MUTEX_INITIALIZER;

typedef struct threadInputSet{
	pthread_mutex_t inputBufLock;
	pBPNode *root;
	keyType key;
	char string[512];
}bufInputSet;

typedef struct sbuf_t{
	pthread_mutex_t sbufLock;
	sem_t slots;
	sem_t items;
	volatile int numItems;
	bufInputSet *pBuf[BUFFSIZE];
	int n;		//Maximum number of slots
	int head;	//
	int tail;
}sbuf_t;

sbuf_t sbuf;
//use read write lock to protect
pthread_rwlock_t fileEndFlagLock;// = PTHREAD_RWLOCK_INITIALIZER;
volatile _Bool fileEndFlag = false;
pthread_rwlock_t treeLock = PTHREAD_RWLOCK_INITIALIZER;

void buildTree(pBPNode *root);
void insert(bufInputSet *parameter);

void BPTreeInsertNotFull(pBPNode *root,BPNode *node,keyType key,char *string);
void BPTreeSplitInternal(pBPNode *tree,BPNode *parent,BPNode *node,int index);
void BPTreeSplitLeaf(pBPNode *tree,BPNode *parent,BPNode *node,int index);

void printTree(BPNode *tree);

BPNode *callocNewNode(_Bool isLeaf);

void sbufInit(sbuf_t *sp,int n);
void sbufDeinit(sbuf_t *sp);
void sbufInsert(sbuf_t *sp,bufInputSet *item);
bufInputSet* sbufRemove(sbuf_t *sp);
void *thread(void *vargp);

int main(int argc,char **argv)
{
	pthread_t tid[NTHREADS];
	int error;
	BPNode *bRoot = NULL;

	freopen("./trace.csv","w+",stdout);

	pthread_rwlock_init(&fileEndFlagLock,NULL);
	sbufInit(&sbuf,BUFFSIZE);

	for(int i=0;i<NTHREADS;i++){
		error = pthread_create(&tid[i],NULL,thread,NULL);
		if(error != 0)
			perror("thread Create");
	}

	buildTree(&bRoot);

	for(int i=0;i<NTHREADS;i++){
		pthread_join(tid[i],NULL);
	}

	printTree(bRoot);
	time_t timer;
	struct tm *tblock;
	timer = time(NULL);
	tblock = localtime(&timer);
	printf("#######################################");
	printf("\nlocal time is: %s",asctime(tblock));
	fclose(stdout);
	exit(0);
}
void lockBufInit(lockBuf_t *lp)
{
	pthread_mutex_init(&lp->lockBufLock,NULL);
	lp->head = lp->tail = 0;
}
void lockBufEnqueue(lockBuf_t *lp,BPNode *node)
{
	pthread_mutex_lock(&lp->lockBufLock);
	//pthread_rwlock_wrlock(&node->nodeLock);
	lp->lockQueueBuf[lp->tail] = node;
	++lp->tail;
	pthread_mutex_unlock(&lp->lockBufLock);
}
void lockBufAllDequeue(lockBuf_t *lp)
{
	pthread_mutex_lock(&lp->lockBufLock);
	int items = lp->tail;
	while(lp->head < items){
		pthread_rwlock_unlock(&lp->lockQueueBuf[lp->head]->nodeLock);
		lp->lockQueueBuf[lp->head] = NULL;
		++lp->head;
	}
	lp->tail = lp->head = 0;
	pthread_mutex_unlock(&lp->lockBufLock);
}
void sbufInit(sbuf_t *sp,int n)
{
	sp->n = n;
	sp->head = sp->tail = 0;
	sp->numItems = 0;
	//sem_init(&sp->mutex,0,1);//for locking
	pthread_mutex_init(&sp->sbufLock,NULL);
	sem_init(&sp->slots,0,n);//Initially, buf has n empty slots
	sem_init(&sp->items,0,0);//Initially, buf has zero data item;
}
void sbufDeinit(sbuf_t *sp)
{
	//free(sp->pBuf);
}
void sbufInsert(sbuf_t *sp,bufInputSet *item)
{
	sem_wait(&sp->slots);
	pthread_mutex_lock(&sp->sbufLock);
	++sp->numItems;
	//queue,enqueue
	sp->pBuf[sp->tail] = item;
	if(sp->tail == (sp->n-1)){
		sp->tail = 0;
	} else {
		++sp->tail;
	}
	pthread_mutex_unlock(&sp->sbufLock);
	sem_post(&sp->items);//
}

bufInputSet* sbufRemove(sbuf_t *sp)
{
	bufInputSet *item = NULL;
	int semFlag;
	pthread_rwlock_rdlock(&fileEndFlagLock);
	_Bool endFlag =  fileEndFlag;
	pthread_rwlock_unlock(&fileEndFlagLock);
	pthread_mutex_lock(&sp->sbufLock);
	int itemsNum = sp->numItems;
	pthread_mutex_unlock(&sp->sbufLock);
	if(endFlag && (itemsNum == 0)){
		return NULL;
	} else {
		do{
			semFlag = sem_trywait(&sp->items);
			
			pthread_rwlock_rdlock(&fileEndFlagLock);
			endFlag =  fileEndFlag;
			pthread_rwlock_unlock(&fileEndFlagLock);
			pthread_mutex_lock(&sp->sbufLock);
			itemsNum = sp->numItems;
			pthread_mutex_unlock(&sp->sbufLock);
		}while((semFlag==-1) && !(endFlag && (itemsNum==0)));//
		
		if(endFlag && itemsNum == 0){
			return NULL;
		} else {
			pthread_mutex_lock(&sp->sbufLock);
			--sp->numItems;
			//queue dequeue
			item = sp->pBuf[sp->head];
			if(sp->head == (sp->n-1)){
				sp->head = 0;
			} else {
				++sp->head;
			}
			pthread_mutex_unlock(&sp->sbufLock);
			sem_post(&sp->slots);

			return item;
		}
	}
	return item;
}

void buildTree(pBPNode *root)
{
	FILE *pfile = fopen("./assgn_bplus_data.txt","r");
	if(pfile == NULL){
		perror("./assgn_bplus_data.txt");
		exit(1);
	}
	keyType key;
	char keyString[128];
	char dataString[512];
	while(fscanf(pfile,"%s	%s",keyString,dataString) != EOF){
		key = atof(keyString);
		bufInputSet *pParameter = (bufInputSet *)calloc(sizeof(bufInputSet),1);
		pParameter->root = root;
		pParameter->key = key;
		strncpy(pParameter->string,dataString,512);
		//printf("%f,%s\n",pParameter->key,pParameter->string);
		sbufInsert(&sbuf,pParameter);
	}
	pthread_rwlock_wrlock(&fileEndFlagLock);
	fileEndFlag = true;
	pthread_rwlock_unlock(&fileEndFlagLock);
	fclose(pfile);
}

void *thread(void *vargp)
{
	bufInputSet *tmp = NULL;
	//bufInputSet parameter;//结构体赋值的问题,struct copy by bit
	
	while(1){
		tmp = (sbufRemove(&sbuf));
		if(tmp == NULL){
			break;
		}
		//parameter = *tmp;
		//free(tmp);
		//printf("thread ID%x,%f,%s\n",(int)pthread_self(),tmp->key,tmp->string);
		//pthread_rwlock_wrlock(&treeLock);
		insert(tmp);
		//pthread_rwlock_unlock(&treeLock);
	}
	//printf("thread ID%x terminal\n",(int)pthread_self());
	return NULL;
}

void insert(bufInputSet *parameter)
{
	pthread_rwlock_wrlock(&treeLock);

	pBPNode *tree = parameter->root;
	keyType key = parameter->key;
	char string[512];
	strncpy(string,parameter->string,512);
	free(parameter);
	BPNode *root = *tree;
	
	pthread_rwlock_unlock(&treeLock);
	
	//build root node
	if(root == NULL){
		pthread_rwlock_wrlock(&treeLock);
		if(root == NULL){
			root = callocNewNode(true);
			root->numKeys = 1;
			root->keys[0] = key;
			strcpy(root->dataStr[0],string);
			*tree = root;
			pthread_rwlock_unlock(&treeLock);
			return;
		} else{
			pthread_rwlock_unlock(&treeLock);
		}
	} else if(root != NULL){

		//pthread_rwlock_wrlock(&root->nodeLock);//root splited, then root is not root
		//pthread_rwlock_wrlock(&treeLock);
		
		root = *tree;
		BPTreeInsertNotFull(tree,root,key,string);

		//pthread_rwlock_unlock(&treeLock);

	}
}

void BPTreeInsertNotFull(pBPNode *tree,BPNode *pNode,keyType key,char *string)
{

//	pthread_rwlock_wrlock(&treeLock);
	
	BPNode *currentNode = pNode;
	lockBuf_t lockBuf;

	lockBufInit(&lockBuf);

	//set lock at the root node
	pthread_rwlock_wrlock(&currentNode->nodeLock);
	lockBufEnqueue(&lockBuf,currentNode);

	while(!currentNode->leaf){
		int i = currentNode->numKeys - 1;
		while((i >= 0) && (key < currentNode->keys[i])){
			--i;
		}
		++i;
		//set lock at the present node corresponding child node
	//	pthread_rwlock_wrlock(&currentNode->childNode[i]->nodeLock);
		
		currentNode = currentNode->childNode[i];
		//if present node is confidenceable
		if(currentNode->numKeys < (ORDER-1)){
			//release all lock of ancestor
	//		lockBufAllDequeue(&lockBuf);
		}
		//let the child node, to be current node
		//currentNode = currentNode->childNode[i];

	//	lockBufEnqueue(&lockBuf,currentNode);

	}

	//lockBufAllDequeue(&lockBuf);

	int i = currentNode->numKeys - 1;
	while((i >= 0) && (key < (currentNode->keys[i]))){
		currentNode->keys[i+1] = currentNode->keys[i];
		strcpy(currentNode->dataStr[i+1],currentNode->dataStr[i]);
		--i;
	}
	currentNode->keys[i+1] = key;
	strcpy(currentNode->dataStr[i+1],string);
	++currentNode->numKeys;
	
	//split if required
	int nums = currentNode->numKeys;
	if(nums >= ORDER){
		//leaf node is root 
		if(currentNode->parentNode == NULL){
			BPNode *newParent = callocNewNode(false);
			newParent->numKeys = 0;
			newParent->childNode[0] = currentNode;
			*tree = newParent;
			BPTreeSplitLeaf(tree,newParent,currentNode,0);
		} else {
			int i = currentNode->parentNode->numKeys - 1;
			keyType indexKey = currentNode->keys[ORDER/2];
			while((i >= 0) && (indexKey < currentNode->parentNode->keys[i])){
				--i;
			}
			++i;
			BPTreeSplitLeaf(tree,currentNode->parentNode,currentNode,i);
		}
	}

	lockBufAllDequeue(&lockBuf);
//	pthread_rwlock_unlock(&treeLock);
}
void BPTreeInsertInternalNode(pBPNode *tree,BPNode *parent,BPNode *newNode,
		keyType pointValue,int index)
{
	//index location should insert
	for(int i = parent->numKeys; i > index; --i){
		parent->childNode[i+1] = parent->childNode[i];
	}
	parent->childNode[index+1] =  newNode;
	//parent->keys[index] = node->keys[ORDER/2];
	for(int i = (parent->numKeys - 1);i >= index; --i){
		parent->keys[i+1] = parent->keys[i];
	}
	parent->keys[index] = pointValue;//newNode->keys[0];
	++parent->numKeys;

	if(parent->numKeys >= ORDER){
		//node is root, malloc new root node
		if(parent->parentNode == NULL){
			BPNode *newParent = callocNewNode(false);
			newParent->numKeys = 0;
			newParent->childNode[0] = parent;
			*tree = newParent;
			BPTreeSplitInternal(tree,newParent,parent,0);//newParent
		} else {
			int i = parent->parentNode->numKeys - 1;
			keyType indexKey = parent->keys[ORDER/2];
			while((i >= 0) && (indexKey < parent->parentNode->keys[i])){
				--i;
			}
			++i;
			BPTreeSplitInternal(tree,parent->parentNode,parent,i);
		}
	}
}

void BPTreeSplitLeaf(pBPNode *tree,BPNode *parent,BPNode *node,int index)
{
	//new node as right node
	BPNode *newNode = callocNewNode(true);
	//assign the parent
	newNode->parentNode = parent;
	newNode->numKeys = ORDER - ORDER/2;//lowBound
	//node right half transform to newNode
	for(int i = ORDER/2; i < ORDER; i++){
		newNode->keys[i-ORDER/2] = node->keys[i];
		strcpy(newNode->dataStr[i-ORDER/2],node->dataStr[i]);
		node->keys[i] = 0;
		strcpy(node->dataStr[i],"#");
	}
	//resize the temporay node
	node->numKeys = (ORDER/2);
	//set parent node`s child node
	parent->childNode[index] = node;
	//assign the parent
	node->parentNode = parent;

	//deal with parent
	 BPTreeInsertInternalNode(tree,parent,newNode,newNode->keys[0],index);

 	 //link up the leaves
	newNode->prevNode = node;
	if(node->nextNode != NULL){//nextNode != NULL
		node->nextNode->prevNode = newNode;
	}
	newNode->nextNode = node->nextNode;
	node->nextNode = newNode;
}
void BPTreeSplitInternal(pBPNode *tree,BPNode *parent,BPNode *node,int index)
{
	BPNode *newNode = callocNewNode(false);
	//fix the keys of new node
	//ORDER/2-1 key
	keyType startPointValue = node->keys[ORDER/2];
	for(int i = ORDER/2; i < ORDER; i++){
		newNode->keys[i-ORDER/2] = node->keys[i+1];//middle value of interl node
		node->keys[i] = 0;
	}
	//resize the keys of node and new node
	node->numKeys = ORDER/2;
	newNode->numKeys = ORDER/2-1;
	//patition children for the new node
	for(int i = ORDER/2;i < ORDER; i++){
		newNode->childNode[i-ORDER/2] = node->childNode[i+1];
		newNode->childNode[i-ORDER/2]->parentNode = newNode;
		node->childNode[i+1] = NULL;
	}
	//fix children for the current node 
	//if the current node is not the root node
	if(node->parentNode != NULL){
		//assign parents
		newNode->parentNode = parent;
		//insert to parent node(root)
		BPTreeInsertInternalNode(tree,parent,newNode,startPointValue,index);
	} else {
		//set new parent node
		parent->leaf = false;
		//assign parents,
		node->parentNode = parent;
		newNode->parentNode = parent;
		//insert child
		parent->childNode[0] = node;
		parent->childNode[1] = newNode;
		//insert the key into the keys
		parent->keys[0] = startPointValue;
		++parent->numKeys;
	}
}
BPNode *callocNewNode(_Bool isLeaf)
{
	BPNode *newNode = (pBPNode)calloc(sizeof(BPNode),1);
	if(!newNode){
		perror("calloc new node");
		exit(1);
	}
	newNode->leaf = isLeaf;
	pthread_rwlock_init(&newNode->nodeLock,NULL);

	return newNode;
}
void printTree(BPNode *tree)
{
	BPNode *node = tree;
	while(node->childNode[0] != NULL){
		node = node->childNode[0];
	}
	while(node != NULL){
		int nums = node->numKeys;
		for(int i = 0;i < nums; i++){
			printf("%f,%s\n",node->keys[i],node->dataStr[i]);
		}
		node = node->nextNode;
	}
}

